Primeira Prova – 2016 – 18/10/2016

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS CAMPUS VII - UNIDADE TIMÓTEO

Disciplina: Algoritmos e Estrutura de Dados Professor: Aléssio M. Júnior Curso: Engenharia | Regime: Integral | Turno: Diurno

Nome: ___________________________ Matrícula: ____________ Valor: 30 pontos

1. Explique a relação íntima entre Problemas, Algoritmos, hardware e Estruturas de Dados, levando em consideração aspectos de escolha, dependência e representações, usando exemplos e cenários de utilização envolvendo árvores. É possível em uma análise e escolha de solução levar em consideração só um destes requisitos? (4pts)

2. Monte graficamente as seguintes árvores AVL e RubroNegra para as inserções {7,2,1,3,6,9,5} identificando possíveis rotações ou operações importantes. (5pts)

3. Em um jogo Cefetmon Go, (onde um mapa é representado por estruturas hierárquicas baseadas em divisões de cidades, país, bairros, ruas e até quarteirões), você tem que mapear aleatoriamente no mapa pequenos alunos monstros, professores e diretores distribuídos aleatoriamente. Alguns destes seres podem ser chamados de Alunos MorcegosChu, SangueSugaMon, FaçotudoSauro, FaladoresDude, Professores Mongos e assim por diante, cada um com suas pontuações e características que possibilitam o jogo. É um jogo de RPG mundialmente famoso com milhares de monstros que são posicionados e Bilhares de jogadores procurando estes seres. Ao inicializar o servidor e com tempo suficiente, foi criado um grande mapa com todos os monstros distribuídos e ao longo da execução, aleatoriamente, são feitas novas inserções e remoções na medida que jogadores capturam alguns destes monstros, pois o servidor não deverá ser desligado. O mapa em geral sofre operações, pois os jogadores estão continuamente andando pelas áreas do jogo e buscando por monstros próximos. (8Pts)

a. Baseado em características acima e outras que você tem liberdade para poder argumentar; dentro das estruturas estudadas; como você escolheria a melhor estrutura de dados para representar o mapeamento de jogadores e monstros.
b. Justifique por que sua estrutura é adequada e por que ela é melhor do que outras nas funções básicas como busca, manutenção da árvore, proximidade.
c. Você acha que seria interessante manter e usar duas estruturas de dados diferentes para que o jogo tenha bom desempenho?
d. Você consegue desenhar algum cenário em que estruturas de Hash fossem úteis? Como poderiam ser utilizadas?

4. Explique a relação entre árvores Patrícias, Árvores B e Árvores binárias de busca. Como elas trabalham para tirar proveito das diferenças e de suas características para serem aplicadas em cenários com benefícios. (7pts)

5. Como a relação preponderante de custo de operações pode mudar a escolha de uma estrutura de dados dentro de um mesmo problema. (4pts)

6. Insira as seguintes chaves em uma Árvore Patrícia: (4pts) - A -> 000100 - B -> 010100 - C -> 000010 - D -> 100100 - E -> 001001 - F -> 001100 - G -> 101000 - H -> 101010